FLOW15 汽车加油驾驶问题

模型：

分层图最短路径->最短路径

题意：

给定一个 $N×N$ 的方形网格，设其左上角为起点，坐标为 $(1,1)$ ，X 轴向右为正， Y 轴向下为正，每个方格边长为 1 。 一辆汽车从起点出发驶向右下角终点 $(N,N)$ 。 在若干个网格交叉点处，设置了油库。汽车在行驶过程中应遵守如下规则：汽车只能沿网格边行驶，装满油后能行驶 $K$ 条网格边；出发时汽车已装满油，在起点与终点处不设油库； 汽车经过一条网格边时，若其 X 坐标或 Y 坐标减小，则应付费用 $B$ ，否则免付费用； 汽车在行驶过程中遇油库则应加满油并付加油费用 $A$；在需要时可在网格点处增设油库，并付增设油库费用 $C$ (不含加油费用 $A$ )。 求出汽车从起点出发到达终点的一条所付费用最少的行驶路线。

题解：

又是一道假网络流题

一道分层图最短路题

对于k步的条件，我们将原图拆成k+1层图，从下到上第i层表示此时的油够走k-i+1步

对于每个格子

• 都要从下往上将自己的每一层都连起来，代价为0
• 向下向右连边没有代价，向上向左连边代价为$B$

对于加油站

• 这格上的每一层都要向第一层连边，代价为$A$
• 向四周连边时，都是从自己的第一层，到目标的第二层，因为从自己这出去肯定是满油的

对于普通格

• 自己的每一层i都要向四周的更高层i+1连边，因为剩余多少步数都是有可能的
• 还要从自己的每一层向自己的第一层连边，代价为$A+C$，意思是建个加油站加满油

跑一遍最短路，再从每一层的终点处搜集最小的答案即可

代码：

#include <bits/stdc++.h>
using namespace std;
template<class t> inline t read(t &x){
    char c=getchar();bool f=0;x=0;
    while(!isdigit(c)) f|=c=='-',c=getchar();
    while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
    if(f) x=-x;return x;
}
template<class t> inline void write(t x){
    if(x<0) putchar('-'),write(-x);
    else{if(x>9) write(x/10);putchar('0'+x%10);}
}

const int N=2e5+5;
int n,k,a,b,c,dis[N],h[N],en,ans=0x3f3f3f3f;

struct edge{
    int n,v,w;
}e[60*N];

void add(int x,int y,int z){
    e[++en]=(edge){h[x],y,z};
    h[x]=en;
}

int calc(int x,int y,int lv){
    return n*n*(lv-1)+(x-1)*n+y;
}

struct node{
    int x,v;
    inline bool operator < (const node &nt) const {
        return v>nt.v;
    }
};

void dij(int s){
    priority_queue<node> q;
    memset(dis,0x3f,sizeof dis);
    dis[s]=0;
    q.push((node){s,0});
    while(!q.empty()){
        node x=q.top();
        q.pop();
        if(dis[x.x]!=x.v) continue;
        for(int i=h[x.x];i;i=e[i].n){
            int y=e[i].v;
            if(dis[x.x]+e[i].w<dis[y]){
                dis[y]=dis[x.x]+e[i].w;
                q.push((node){y,dis[y]});
            }
        }
    }
}

signed main(){
    read(n);read(k);read(a);read(b);read(c);
    for(int i=1,x;i<=n;i++)
        for(int j=1;j<=n;j++){
            read(x);
            for(int l=1;l<=k;l++)
                add(calc(i,j,l),calc(i,j,l+1),0);
            if(x){
                for(int l=2;l<=k+1;l++)
                    add(calc(i,j,l),calc(i,j,1),a);
                if(i<n) add(calc(i,j,1),calc(i+1,j,2),0);
                if(j<n) add(calc(i,j,1),calc(i,j+1,2),0);
                if(i>1) add(calc(i,j,1),calc(i-1,j,2),b);
                if(j>1) add(calc(i,j,1),calc(i,j-1,2),b);
            }
            else{
                for(int l=1;l<=k;l++){
                    if(i<n) add(calc(i,j,l),calc(i+1,j,l+1),0);
                    if(j<n) add(calc(i,j,l),calc(i,j+1,l+1),0);
                    if(i>1) add(calc(i,j,l),calc(i-1,j,l+1),b);
                    if(j>1) add(calc(i,j,l),calc(i,j-1,l+1),b);
                }
                for(int l=2;l<=k+1;l++)
                    add(calc(i,j,l),calc(i,j,1),a+c);
            }
        }
    dij(calc(1,1,1));
    for(int i=1;i<=k+1;i++)
        ans=min(ans,dis[calc(n,n,i)]);
    write(ans);
}